public class knutMorris {

	private String text;
	private String pattern;
	private int pos;
	private int comparisons;

	public knutMorris(String txt, String pattern) {
		this.text = txt;
		this.pattern = pattern;
		initKMP();
	}

	private void initKMP() {
		int i = 0;
		int j = 0;
		

		int[] shift = initShift();

		while (j < pattern.length() && i < text.length()) {
			comparisons++;
			if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
				i++;
				j++;

			} else {

				j = shift[j];
			}

		}
		if (j == pattern.length()) {
			this.pos = i - pattern.length();
		} else {
			this.pos = -1;
		}

	}

	private int[] initShift() {
		int[] shift = new int[pattern.length()];
		int i = 0;
		int j = -1;
		shift[0] = -1;

		while (i < (pattern.length() - 1)) {
			if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
				i++;
				j++;
				shift[i] = j;
			} else {
				shift[i] = j;
			}
		}
		return shift;
	}

	@Override
	public String toString() {
		return "KMP:\t\terstes auftreten bei: " + pos + " und vergleiche: "
				+ comparisons;
	}
}
